import java.util.Stack;

public class DecodeString {
    public String decodeString(String s) {
        // string 栈存放需要重复的字符串
        // int 栈则存对应字符串要重复的次数
        Stack<StringBuilder> str = new Stack<>();
        Stack<Integer> nums = new Stack<>();

        // 存入一个空串, 防止越界错误
        StringBuilder space = new StringBuilder("");
        str.push(space);

        int i = 0, n = s.length();
        char[] ch = s.toCharArray();
        while(i < n) {
            if(ch[i] >= '0' && ch[i] <= '9') {
                // 如果属于数字, 则提取出数字, 放到 int 栈中
                int tmp = 0;
                while(i < n && ch[i] >= '0' && ch[i] <= '9') {
                    tmp = tmp * 10 + (ch[i] - '0');
                    i++;
                }
                nums.push(tmp);
            }else if(ch[i] == '[') {
                // 如果当前字符为 [ 左方括号, 则提取出后面的小写英文字母, 放到 string 栈中
                i++;
                StringBuilder tmp = new StringBuilder();
                while(i < n && ch[i] >= 'a' && ch[i] <= 'z') {
                    tmp.append(ch[i]);
                    i++;
                }
                str.push(tmp);
            }else if(ch[i] == ']') {
                // 如果是 ] 右方括号, 则拿出两个栈的栈顶元素, 进行 "解码"
                StringBuilder repeat = str.pop();
                int time = nums.pop();
                StringBuilder tmp = new StringBuilder();
                while(time != 0) {
                    tmp.append(repeat);
                    time--;
                }

                // 将解码后的字符串, 添加到栈顶元素后面
                str.peek().append(tmp);
                i++;
            }else if(ch[i] >= 'a' && ch[i] <= 'z') {
                // 如果当前字符只是普通字符, 不需要解码, 则提取出来, 添加到str字符串栈顶元素后面
                StringBuilder tmp = new StringBuilder();
                while(i < n && ch[i] >= 'a' && ch[i] <= 'z') {
                    tmp.append(ch[i]);
                    i++;
                }

                // 将解码后的字符串, 添加到栈顶元素后面
                str.peek().append(tmp);
            }
        }
        return str.pop().toString();
    }
}
